//Fri Jun 10 22:01:28 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class State{
public:
	int x1, y1, x2, y2;
	int steps;
	State(int a, int b, int c, int d, int s){
		x1 = a;
		y1 = b;
		x2 = c;
		y2 = d;
		steps = s;
	}
};

class PathFinding {
public:
	int M;
	int N;
	bool checkBound(int x, int y){
		return x>=0 && x< M && y>=0 && y<N;
	}
	int minTurns(vector <string>);
};

bool visited[20][20][20][20];

int PathFinding::minTurns(vector <string> board) {
	M = board.size();
	N = board[0].size();
	memset(visited, false, sizeof(visited));
	int ax, bx, ay, by;
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(board[i][j]=='A') {ax = i; ay = j;}
			if(board[i][j]=='B') {bx = i; by = j;}
		}
	}
	State start(ax, ay, bx, by, 0);
	
	deque<State> q;
	q.push_back(start);
	while(!q.empty()){
		int p1 = q.front().x1;
		int q1 = q.front().y1;
		int p2 = q.front().x2;
		int q2 = q.front().y2;
		int stp = q.front().steps;
		q.pop_front();
		if(p1==p2 && q1==q2) continue;
		if(p1==bx && q1==by && p2==ax && q2==ay) return stp;
		if(visited[p1][q1][p2][q2]) continue;
		visited[p1][q1][p2][q2] = true;
		
		for(int dx1 = -1; dx1<=1; dx1++){
			for(int dy1=-1; dy1<=1; dy1++){
				for(int dx2=-1; dx2<=1; dx2++){
					for(int dy2=-1; dy2<=1; dy2++){
						int xx1 = p1 + dx1;
						int yy1 = q1 + dy1;
						int xx2 = p2 + dx2;
						int yy2 = q2 + dy2;
						if(xx1==p2 && yy1==q2 && xx2==p1 && yy2==q1) continue;
						if(checkBound(xx1, yy1) && checkBound(xx2, yy2)){
							if(board[xx1][yy1]=='X' || board[xx2][yy2]=='X') continue;
							State tmp(xx1, yy1, xx2, yy2, stp+1);
							q.push_back(tmp);
						}
					}
				}
			}
		}
	}
	return -1;
}

//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
